package solution;

import solution.util.TreeNode;

import java.util.ArrayList;


/**
 * @author or2
 * @date 2021/7/30 20:24
 */
public class PathSum {

    /**
     *
     * @param root TreeNode类
     * @param sum int整型
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> pathSum (TreeNode root, int sum) {
        ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
        ArrayList<Integer> tempAns = new ArrayList<>();

        if (root == null) {
            return ans;
        }

        int temp = 0;

        findAns(root, temp, ans, sum, tempAns);

        return ans;
    }

    /**
     * 先序递归
     * @param node 当前递归结点
     * @param tempSum 记录当前走过路径上的总权值
     * @param ans 记录答案的数组
     * @param sum 目标-所要查找的路径总权值
     * @param tempAns 记录走过的路径
     */
    private void findAns(TreeNode node, int tempSum, ArrayList<ArrayList<Integer>> ans, int sum, ArrayList<Integer> tempAns) {
        if (node != null) {
            ArrayList<Integer> clone = (ArrayList<Integer>) tempAns.clone();
            clone.add(node.val);
            tempSum += node.val;
            if (tempSum == sum && node.left == null && node.right == null) {
                ans.add(clone);
            }

            findAns(node.left, tempSum, ans, sum, clone);
            findAns(node.right, tempSum, ans, sum, clone);
        }
    }
}
